package com.li.list;

public class 复杂链表的复制 {
	public static void main(String[] args) {
		RNode root = new RNode();
		RNode RNode1 = new RNode(1);
		RNode RNode2 = new RNode(2);
		RNode RNode3 = new RNode(3);
		RNode RNode4 = new RNode(4);
		RNode RNode5 = new RNode(5);
		RNode RNode6 = new RNode(6);
		
		root.next = RNode1;
		RNode1.next = RNode2;
		RNode2.next = RNode3;
		RNode3.next = RNode4;
		RNode4.next = RNode5;
		RNode5.next = RNode6;
		RNode1.random = RNode3;
		RNode2.random = RNode5;
		
		printList(root);
	}
	
	/**
	 * 打印链表
	 * @param head
	 */
	public static void printList(RNode head){
		while((head = head.next)!=null){
			System.out.print(head.label+" ");
			if(head.random!=null){
				System.out.print(head.random.label+"#");
			}
		}
		System.out.println();
	}
	
	public static RNode Clone(RNode pHead){
        if(pHead==null)
            return null;
        RNode pCur = pHead;
        //复制next 如原来是A->B->C 变成A->A'->B->B'->C->C'
        while(pCur!=null){
            RNode RNode = new RNode(pCur.label);
            RNode.next = pCur.next;
            pCur.next = RNode;
            pCur = RNode.next;
        }
        pCur = pHead;
        //复制random pCur是原来链表的结点 pCur.next是复制pCur的结点
        while(pCur!=null){
            if(pCur.random!=null)
                pCur.next.random = pCur.random.next;
            pCur = pCur.next.next;
        }
        RNode head = pHead.next;
        RNode cur = head;
        pCur = pHead;
        //拆分链表
        while(pCur!=null){
            pCur.next = pCur.next.next;
            if(cur.next!=null)
                cur.next = cur.next.next;
            cur = cur.next;
            pCur = pCur.next;
        }
        return head;       
    }
	
}

class RNode{
    int label;
    RNode next = null;
    RNode random = null;
 
    RNode(int label) {
        this.label = label;
    }
    RNode() {
    }
}
